#include<stdio.h>
int g[3][5]={{2,4,7,11},{5,10,16,20},{8,12,17,22}};
int n=3;
int c=10;
int m[100][100]={0};
int s[100][100]={0};
void Knapsack()
{
	int j,q,i,k=0,u;
	for(q=0;q<=c;q++) 
	{	
		if(q-k*k>=0)
		{
			m[1][q]=g[0][k];
			s[1][q]=k;k++;
		}
		else 
		{
			m[1][q]=g[0][k-1];
			s[1][q]=k-1;
		}
	}
	for(i=2;i<=n;i++)
	{
		k=1;
		for(j=0;j<=c;j++)
		{
			m[i][j]=m[i-1][j]+g[i-1][0];
			for(q=0;q<=k-1;q++)
			{
				if(m[i-1][j-q*q]+g[i-1][q]>m[i][j])
				{
					m[i][j]=m[i-1][j-q*q]+g[i-1][q];
				    s[i][j]=q;
				}
			}
			if(j-k*k>=0) k++;
		}
	}
}
int main()
{	
	int i,j;
	Knapsack();
	for(j=1;j<=3;j++)
	{
		for(i=0;i<=10;i++)
		printf("%d ",m[j][i]);
		printf("\n");
	}
	printf("ss\n");
	for(j=1;j<=3;j++)
	{
		for(i=0;i<=10;i++)
			printf("%d ",s[j][i]);
		printf("\n");
	}
	printf("11");
}
